﻿#pragma once
#include<iostream>
#include<vector>
using namespace std;
// 哈希函数：除法散列法/除留余数法，h(key) = key % M
// 当使⽤除法散列法时，建议M取不太接近2的整数次幂的⼀个质数(素数)。

// 解决哈希冲突方法：开放定址法

//面试题：哈希表对key值的要求？
//1、key是能够转成整形的，如果不能转成整形要提供对应的仿函数
//2、key是能够支持等于比较的，如果不能支持等于比较要提供对应的仿函数

//面试题：红黑树对key值的要求？
// key是能够支持比较大小的，至少支持一个大于或小于的比较（反个方向就是另一种比较了），如果不能支持要提供对应的仿函数


enum State
{
	EXIST,
	EMPTY,
	DELETE
};

template<class K, class V>
struct HashData
{
	pair<K, V> _kv;
	State _state = EMPTY;
};

template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

template<>  //因为string用的比较多，所以我们可以专门搞一个模板特化版本，专门针对string。有特化走特化，没特化走普通类型。
struct HashFunc<string>
{
	// 尽量要控制不要重复  
	// 1、将字符串的所有ASCII码加起来 
	// 2、但是加起来之后，对于字符相同但是顺序不同的字符串还是不太好区分，所以这里要用BKDR哈希算法
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (auto ch : s) //将字符串转化成整型，通过映射整型去找到字符串对应的位置
		{
			hash += ch; //但是光有这一句代码的话，应对一些字符相同但是顺序不同的字符串的时候，仍然是不好区分的 
			hash *= 131; //BKDR哈希 
		}
		return hash;
	}
};

namespace open_address
{
	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
	public:
		HashTable()
			:_tables(__stl_next_prime(0)), _n(0)
		{}

		// 素数表（选不太接近2的次方的那个素数）。这是C++的SGI版实现哈希表的方法.
		inline unsigned long __stl_next_prime(unsigned long n)
		{
			//  Note: assumes long is at least 32 bits.
			static const int __stl_num_primes = 28;
			static const unsigned long __stl_prime_list[__stl_num_primes] =
			{
				53, 97, 193, 389, 769,
				1543, 3079, 6151, 12289, 24593,
				49157, 98317, 196613, 393241, 786433,
				1572869, 3145739, 6291469, 12582917, 25165843,
				50331653, 100663319, 201326611, 402653189, 805306457,
				1610612741, 3221225473, 4294967291
			};

			const unsigned long* first = __stl_prime_list;
			const unsigned long* last = __stl_prime_list + __stl_num_primes;
			const unsigned long* pos = lower_bound(first, last, n);
			return pos == last ? *(last - 1) : *pos;
		}

		bool Insert(const pair<K, V>& kv)
		{
			// 不允许冗余
			if (Find(kv.first))
				return false;

			// 负载因子 >= 0.7扩容
			if (_n * 10 / _tables.size() > 7)
			{
				// 复用Insert
				HashTable<K, V, Hash> newht;
				newht._tables.resize(__stl_next_prime(_tables.size() + 1)); //这里需要+1，因为lower_bound获取的是大于等于n的第一个值
				for (auto& data : _tables)
				{
					// 旧表的数据映射到新表
					if (data._state == EXIST)
					{
						newht.Insert(data._kv);
					}
				}
				_tables.swap(newht._tables);
			}

			Hash hash;
			size_t hash0 = hash(kv.first) % _tables.size(); // 这里要模size。因为顺序表要求要挨着，在size的位置线性存储，后面的空间（size和capacity之间的空间）是给你预留的。
			size_t hashi = hash0;
			size_t i = 1;
			int flag = 1;
			while (_tables[hashi]._state == EXIST)
			{
				// 线性探测
				hashi = (hash0 + i) % _tables.size();
				++i;

				// 二次探测
				/*hashi = (hash0 + (i*i*flag)) % _tables.size();
				if (hashi < 0)
					hashi += _tables.size();
				if (flag == 1)
				{
					flag = -1;
				}
				else
				{
					++i;
					flag = 1;
				}*/
			}
			_tables[hashi]._kv = kv;
			_tables[hashi]._state = EXIST;
			++_n;
			return true;
		}

		HashData<K, V>* Find(const K& key)
		{
			Hash hash;
			size_t hash0 = hash(key) % _tables.size();
			size_t hashi = hash0;
			while (_tables[hashi]._state != EMPTY)
			{
				if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key) // 哈希表里的元素要支持等于比较，不支持时要自己给仿函数
				{
					return &_tables[hashi];
				}

				// 线性探测
				hashi = (hashi + 1) % _tables.size();
			}
			return nullptr;
		}

		bool Erase(const K& key)
		{
			HashData<K, V>* ret = Find(key);
			if (ret)
			{
				ret->_state = DELETE;
				return true;
			}
			else
			{
				return false;
			}
		}

	private:
		vector<HashData<K, V>> _tables;
		size_t _n = 0; // 记录数据个数
	};
}

namespace hash_bucket
{
	template<class K, class V>
	struct HashNode
	{
		pair<K, V> _kv;
		HashNode<K, V>* _next; //这里使用单链表，库里面也用的单链表，所以unorder_map的迭代器是一个单向迭代器

		HashNode(const pair<K, V>& kv)
			:_kv(kv)
			, _next(nullptr)
		{}
	};

	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
		typedef HashNode<K, V> Node;
		inline unsigned long __stl_next_prime(unsigned long n)
		{
			static const int __stl_num_primes = 28;
			static const unsigned long __stl_prime_list[__stl_num_primes] =
			{
				53, 97, 193, 389, 769,
				1543, 3079, 6151, 12289, 24593,
				49157, 98317, 196613, 393241, 786433,
				1572869, 3145739, 6291469, 12582917, 25165843,
				50331653, 100663319, 201326611, 402653189, 805306457,
				1610612741, 3221225473, 4294967291
			};
			const unsigned long* first = __stl_prime_list;
			const unsigned long* last = __stl_prime_list +__stl_num_primes;
			const unsigned long* pos = lower_bound(first, last, n);
			return pos == last ? *(last - 1) : *pos;
		}
	public:
		HashTable()
		{
			_tables.resize(__stl_next_prime(0), nullptr);
		}

		// 拷⻉构造和赋值拷⻉需要实现深拷⻉

		~HashTable()
		{
			// 依次把每个桶释放
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_tables[i] = nullptr;
			}
		}

		bool Insert(const pair<K, V>& kv)
		{
			// 不允许冗余
			if (Find(kv.first))
				return false;

			Hash hs;
			size_t hashi = hs(kv.first) % _tables.size();

			// 负载因⼦==1扩容
			if (_n == _tables.size())
			{
				/*HashTable<K, V> newHT;
				newHT._tables.resize(__stl_next_prime(_tables.size()+1);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while(cur)
					{
						newHT.Insert(cur->_kv);
						cur = cur->_next;
					}
				}
				_tables.swap(newHT._tables);*/
				// 这⾥如果使⽤上⾯的⽅法，扩容时创建新的结点，后⾯还要释放旧结点，浪费了
				// 下⾯的⽅法，直接移动旧表的结点到新表，效率更好
				vector<Node*> newtables(__stl_next_prime(_tables.size() + 1), nullptr);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;
						// 旧表中节点，挪动新表重新映射的位置
						size_t hashi = hs(cur->_kv.first) % newtables.size();
						// 头插到新表
						cur->_next = newtables[hashi];
						newtables[hashi] = cur;
						cur = next;
					}
					_tables[i] = nullptr;
				}
				_tables.swap(newtables);
			}

			// 头插
			Node* newnode = new Node(kv);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_n;
			return true;
		}

		Node* Find(const K& key)
		{
			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					return cur;
				}
				cur = cur->_next;
			}
			return nullptr;
		}

		bool Erase(const K& key)
		{
			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (prev == nullptr) // 删除的是第一个节点
					{
						_tables[hashi] = cur->_next;
					}
					else // 删除的是中间节点
					{
						prev->_next = cur->_next;
					}
					delete cur;
					--_n;
					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}
			return false;
		}
	private:
		vector<Node*> _tables; // 指针数组
		size_t _n = 0; // 表中存储数据个数
	};

}
